package com.aug_leo.datastructure.stack;

import java.util.LinkedList;

/**
 * 逆波兰表达式求值也称为后缀表达式求值
 * <ul>
 *     <li>从左向右进行计算</li>
 *     <li>不必考虑运算符优先级，即不用包含括号</li>
 * </ul>
 * 题目假设
 * <ul>
 *     <li>数字都视为整数</li>
 *     <li>数字和运算符个数给定正确，不会有除零发生</li>
 * </ul>
 */
public class E02Leetcode150 {

    /*

        |   |
        | 13|
        | 4 |
        _____

        "4","13","5","/","+"

        - 遇到数字压入栈
        - 遇到运算符, 就从栈弹出两个数字做运算, 将结果压入栈
        - 遍历结束, 栈中剩下的数字就是结果

        1 + 2 中缀
        1 2 + 后缀
     */

    public int evalRPN(String[] tokens) {
        LinkedList<Integer> stack = new LinkedList<>();
        for (String token : tokens) {
            switch (token) {
                case "+" -> {
                    Integer b = stack.pop();
                    Integer a = stack.pop();
                    stack.push(a + b);
                }
                case "-" -> {
                    Integer b = stack.pop();
                    Integer a = stack.pop();
                    stack.push(a - b);
                }
                case "*" -> {
                    Integer b = stack.pop();
                    Integer a = stack.pop();
                    stack.push(a * b);
                }
                case "/" -> {
                    Integer b = stack.pop();
                    Integer a = stack.pop();
                    stack.push(a / b);
                }
                default -> { // 数字
                    stack.push(Integer.parseInt(token));
                }
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String[] tokens = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
        System.out.println(new E02Leetcode150().evalRPN(tokens));
        tokens = new String[]{"2", "1", "+", "3", "*"};
        System.out.println(new E02Leetcode150().evalRPN(tokens));
    }
}
